/**
 * @author SaoE
 * @date 2025/2/25 20:37
 */
public class _79 {
    boolean flag = false;
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        int[][] visited = new int[m][n];
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                backTrace(board, word, 0, i, j, visited);
                if (flag){
                    return true;
                }
                visited[i][j] = 0;

            }
        }
        return false;
    }

    public void backTrace(char[][] board, String word, int index, int i, int j, int[][] visited){
        if(index >= word.length()){
            flag = true;
            return;
        }
        if (i >= board.length || j >= board[0].length || i < 0 || j < 0 || visited[i][j] == 1){
            return;
        }
        if (board[i][j] == word.charAt(index)){
            visited[i][j] = 1;
            backTrace(board, word, index + 1, i + 1, j, visited);
            backTrace(board, word, index + 1, i - 1, j, visited);
            backTrace(board, word, index + 1, i, j + 1, visited);
            backTrace(board, word, index + 1, i, j - 1, visited);
            if (flag){
                return;
            }
            visited[i][j] = 0;

        }
    }

    public static void main(String[] args) {
        _79 v = new _79();
        char[][] board = new char[3][4];
        board[0] = new char[]{'A', 'B', 'C', 'E'};
        board[1] = new char[]{'S', 'F', 'C', 'S'};
        board[2] = new char[]{'A', 'D', 'E', 'E'};
        System.out.println(v.exist(board, "ABCCED"));
    }
}
